1105D - Kilani and the Game - CodeForces Solution

#include <bits/stdc++.h>
#define F first
#define S second
#define endl "\n";
#define shekoo ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

const int N = 1e3+5, M = 12;
char arr[N][N];
int expansion[M], ans[M], n, m, p, cnt[M];
queue<pair<pi, int>> g[M];
int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};


bool valid(int x, int y){
    return x < n and x >= 0 and y < m and y >= 0 and arr[x][y] == '.';
}

void bfs(int playernum){
    cnt[playernum]++;
    while(!g[playernum].empty()){
        int x = g[playernum].front().F.F, y = g[playernum].front().F.S, step = g[playernum].front().S;
        if(step == (expansion[playernum]*cnt[playernum])) return;
        for(int i=0; i<4; i++){
            int xx = x + d[i][0], yy = y + d[i][1];
            if(valid(xx, yy)){
                arr[xx][yy] = char('0'+playernum);
                g[playernum].push({{xx, yy}, step+1});
            }
        }
        g[playernum].pop();
    }
}

void solve(){
    for(int i=1; i<=p; i++) bfs(i);
    bool f = 0;
    for(int i=1; i<=p; i++){
        if(!g[i].empty()){
            f = 1;
            break;
        }
    }
    if(f) solve();
    else{
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
//                cout << arr[i][j];
                if(arr[i][j] == '.' or arr[i][j] == '#') continue;
                ans[arr[i][j]-'0']++;
            }
//            cout << endl
        }
        for(int i=1; i<=p; i++) cout << ans[i] << " ";
    }
}

int main() {
    shekoo
    cin >> n >> m >> p;
    for(int i=1; i<=p; i++) cin >> expansion[i];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j];
            if(arr[i][j] == '.' or arr[i][j] == '#') continue;
            g[(arr[i][j]-'0')].push({{i, j}, 0});
        }
    }
    solve();
    return 0;
}